import math


class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        facts = [math.factorial(i) for i in range(n - 1, -1, -1)]

        x = k - 1
        decomposed = []
        for fact in facts:
            y = x // fact
            x = x % fact
            decomposed.append(y)

        remain_numbers = list(range(n))
        res = []
        for i in range(n):
            res.append(remain_numbers[decomposed[i]])
            del remain_numbers[decomposed[i]]

        res = ''.join(str(x + 1) for x in res)
        return res


print(Solution().getPermutation(3, 3))








class Solution1:
    def getPermutation(self, n: int, k: int) -> str:
        from itertools import permutations
        perm = permutations(range(n))
        for _ in range(k - 1):
            next(perm)
        res = next(perm)
        res = ''.join(str(x+1) for x in res)
        return res
